package leetcode;

import pojo.ListNode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2022-12-26
 */
public class LeetCode23 {

    public static class NodeComparator implements Comparator<ListNode> {

        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> heap1 = new PriorityQueue<>(new NodeComparator());
        heap1.addAll(Arrays.asList(lists));
        ListNode head = heap1.poll();
        ListNode pre = head;
        if (pre.next != null) {
            heap1.add(pre.next);
        }
        while (!heap1.isEmpty()) {
            ListNode poll = heap1.poll();
            pre.next = poll;
            pre = pre.next;
            if (poll.next != null) {
                heap1.add(poll.next);
            }
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode node2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode node3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = {node1, node2, node3};
        ListNode listNode = mergeKLists(lists);
        while (listNode != null) {
            System.out.println("listNode = " + listNode.val);
            listNode = listNode.next;
        }
    }
}
